\section{Experiments}

In this section, we report the experiment results conducted to test the
efficiency of the algorithm. The experiments are conducted for two queries
on machine-generated XML documents.

\subsection{6.1 Experimental Data and Environment}

The algorithm was implemented in Java. The server ran on a single PC.
The PC has a Intel(R) Core(TM) i5 3.20-3.40GHZ CPU, 8 GB of memory, running on Windows 7 and Java 1.8.
The clients ran on a PC-cluster. The PC-cluster used for our experiments had 16 PCs.
Each PC has an Intel(R) Core(TM) i5 3.30-GHz CPU, 8 GB of memory, and an SSD, running Ubuntu 14.04 LTS (Linux kernel: 3.2.0-48- generic) and Java 1.8. The PCs are connected with Gigabit Ethernet.
The connection between server and clients are 100 Megabyte(?) Ethernet.

For XML files in our experiments, we use the XML files generated by xmlgen,
which is an XML document generator developed under the XMark project.
The xmlgen generates XML documents of different sizes by an input parameter,
through which we can specify the size of the output XML file. In our experiments,
the sizes of XML files created by xmlgen range from 640MB to 8GB.

To show the effectiveness of our parallel XPath query algorithm,
we performed two types of tests. In the first test, we show the scalability of
the algorithm by testing the same file on different number of computers. In the second,
we increase the size of the XML documents for test running on 16 computers.


For the query expressions, we used the following queries.

\small Query-1:  ``\verb|/site/people/person[/profile/gender]/name|''

\verb|Query-2:/site/open_auctions/open_auction/bidde[/following-sibling::bidder|


\small Query-3:  ``\verb|/site/open_auctions/open_auction/bidder[/following-sibling::bidder]|''

\small Query-4:  ``\verb|/site/closed_auctions/closed_auction/annotation/description/text/keyword|''

The first three queries are used for testing the scalability and data processing ability.
The 4th has the most steps. Therefore, we use it to test the cost of
network communications affected by the steps.

\subsection{Scalability}

This first experiment tested the efficiency and parallel speedups of
querying with respect to the number of PCs. The largest size of XML data
on one single computer we have tested is 640MB. We use this data
for testing the performance of the given three queries on 1, 2, 4, 8 and 16 computers.

Due to the split, an XML node may be split into two
open nodes, correspondingly, the content of the XML
node are also split into two pieces. Therefore, one selected
node may be stored on two different cluster nodes. Due to
the names are same, an algorithm is needed to pair up these
split results and collect the split results from split nodes.

Because the computation for pairing the spit nodes
requires the information stored on the whole cluster, we do
the computation on the master PC by sending all the
necessary data to it.

We encode the depth of partial tree, open side and half
content of the selected open node to a string, and then send
it to master PC.

Then on the master PC, we can use this information to
compute the relationship of each pair of node to form the
final result for output.
